#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/

int IsInsertion(ElemSet *a, ElemSet *b, int n);
void NextInsertion(ElemSet *b, int n, int p);
int MergeLength(ElemSet *b, int n);
void TwoWayMerge(ElemSet *a, ElemSet *t, int l, int m, int r);
void NextMerge(ElemSet *b, ElemSet *a, int n);
void PrintResults(ElemSet *a, int n);

int main(void) {
    ElemSet *a, *b;
    int n, i, p;

    scanf("%d", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n); /* a存原始序列 */
    b = (ElemSet *)malloc(sizeof(ElemSet) * n); /* b存中间序列 */
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    p = IsInsertion(a, b, n);
    if (p > 0) { /* 如果是插入排序 */
        NextInsertion(b, n, p); /* 执行下一步插入 */
        PrintResults(b, n); /* 输出结果 */
    } else { /* 否则执行下一步归并 */
        NextMerge(b, a, n); /* 将b中元素归并到a */
        PrintResults(a, n); /* 输出结果 */
    }

    return 0;
}

int IsInsertion(ElemSet *a, ElemSet *b, int n) {
    /* 判断是否插入排序，返回下一个待插入元素的位置 */
    int i, p;

    for (i = 1; i < n; i++) {
        if (b[i] < b[i - 1]) { /* 发现错位 */
            break;
        }
    }
    p = i; /* p为错位位置，即下一轮插入的是a[p] */
    for (; i < n; i++) { /* 继续检查剩下的元素 */
        if (b[i] != a[i]) { /* 发现元素变化了 */
            break;
        }
    }
    if (i < n) {/* 不是插入排序*/
        p = 0; /* 错误标识 */
    }
    return p;
}

void NextInsertion(ElemSet *b, int n, int p) {
    /* 对b[p]执行插入排序*/
    ElemSet t;
    int j;

    printf("Insertion Sort\n");
    t = b[p]; /* 当前待插入的元素 */
    for (j = p; j >= 1; j--) {
        if (b[j - 1] > t) { /* 若不是插入位置 */
            b[j] = b[j - 1]; /* 位移 */
        } else {
            break; /* 找到插入的位置 */
        }
    }
    b[j] = t; /* 插入 */
}

int MergeLength(ElemSet *b, int n) {
    /* 返回归并的有序子列长度 */
    int i, len;

    for (len = 2; len <= n; len <<= 1) { /* 当前段长 */
        for (i = len; i < n; i += (len + len)) {
            if (b[i - 1] > b[i]) { /* 若两段间错位 */
                break;
            }
        }
        if (i < n) {/* 若当前段长下出现段间错位 */
            break;
        }
    }
    return len;
}

void TwoWayMerge(ElemSet *a, ElemSet *t, int l, int m, int r) {
    /* 将a[l~m]与a[m+1~r]归并到t[l~r] */
    int i, j, k;

    i = l;
    j = m + 1;
    k = l;
    while (i <= m || j <= r) {
        if (j > r || (i <= m && a[i] <= a[j])) {
            t[k] = a[i]; /* 将a[i]添加至t末尾 */
            i++;
        } else {
            t[k] = a[j]; /* 将a[j]添加至t末尾 */
            j++;
        }
        k++;
    }
}

int Min(int x, int y) {
    return (x < y) ? x : y;
}

void NextMerge(ElemSet *b, ElemSet *a, int n) {
    /* 执行一步归并排序，从b归并到a中 */
    int sorted_len, l_x, r_x, l_y, r_y, i;

    printf("Merge Sort\n");
    sorted_len = MergeLength(b, n); /* 当前有序子列长度 */
    l_x = 0; /* 左子序列从最左端开始 */
    while (l_x <= (n - 1 - sorted_len)) {
        r_x = l_x + sorted_len - 1; /* 左子序列的右端点 */
        l_y = r_x + 1; /* 右子序列的左端点 */
        r_y = Min(l_y + sorted_len - 1, n - 1); /* 右子序列的右端点 */
        TwoWayMerge(b, a, l_x, r_x, r_y); /* 归并 */
        l_x = r_y + 1; /* 下一对子序列的左子序列的左端点 */
    }
}

void PrintResults(ElemSet *a, int n) {
    /* 输出a[]中的元素 */
    int i;

    printf("%d", a[0]);
    for (i = 1; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
}